package MianShiTi;

public class Test {

    //节点定义为内部类
    class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//代表链表的头结点

    /**
     * 力扣206 翻转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head==null) return head;
        if(head.next==null) return head;
        ListNode cur=head.next;
        ListNode curN=cur.next;
        head.next=null;
        while(cur!=null) {
            curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }

    /**
     * 力扣876 链表的中间节点
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    /**
     * 力扣面试题 02.02. 返回倒数第 k 个节点
     * @param head
     * @param k
     * @return
     */
    //不确定k的合法性
    public int kthToLast(ListNode head, int k) {
        if(k<=0) return -1;
        ListNode fast=head;
        ListNode slow=head;
        int count=k-1;
        while(count!=0) {
            if(fast==null)return -1; //说明k不合法,给得太大了
            fast=fast.next;
            count--;
        }
        while(fast.next!=null) {
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }

    /**
     * 力扣21. 合并两个有序链表
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1=list1;
        ListNode cur2=list2;
        ListNode newHead=new ListNode(0);
        ListNode cur=newHead;
        while(cur1!=null && cur2!=null) {
            if(cur1.val<cur2.val) {
                cur.next=cur1;
                cur1=cur1.next;
            } else {
                cur.next=cur2;
                cur2=cur2.next;
            }
            cur=cur.next;
        }
        if(cur1!=null) {
            cur.next=cur1;
        }
        if(cur2!=null) {
            cur.next=cur2;
        }
        return newHead.next;
    }

    /**
     * 牛客CM11 链表分割
     * @param pHead
     * @param x
     * @return
     */
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null)return null;
        ListNode small=null;
        ListNode head1=null;
        ListNode big=null;
        ListNode head2=null;
        ListNode cur=pHead;
        while(cur!=null) {
            if(cur.val<x) {
                if(small==null) {
                    small=head1=cur;
                } else {
                    small.next=cur;
                    small=small.next;
                }
            } else {
                if(big==null) {
                    big=head2=cur;
                } else {
                    big.next=cur;
                    big=big.next;
                }
            }
            cur=cur.next;
        }
        //将small和big链表连起来
        if(head1==null) return head2;
        else {
            small.next=head2;
            if(head2!=null) {
                big.next=null;
            }
        }
        return head1;
    }

    public boolean chkPalindrome(ListNode head) {
        if(head==null) return true;//空链表认为是回文的
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        //找到了中间节点
        ListNode cur=slow.next;
        while(cur!=null) {
            ListNode curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;
        }
        //链表翻转完了
        ListNode cur2=head;
        while(cur2!=slow) {
            if(cur2.val!=slow.val) return false;
            if(cur2.next==slow) return true;
            cur2=cur2.next;
            slow=slow.next;
        }
        return true;
    }

    /**
     * 力扣141. 环形链表
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null && fast.next.next!=null) {
            fast=fast.next.next.next;
            slow=slow.next.next;
            if(fast==slow)return true;
        }
        return false;
    }

    /**
     * 力扣142. 环形链表 II
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null && fast.next.next!=null) {
            fast=fast.next.next.next;
            slow=slow.next.next;
            if(fast==slow) {
                ListNode cur1=slow;
                ListNode cur2=head;
                while(cur1!=cur2) {
                    cur1=cur1.next;
                    cur2=cur2.next;
                }
                return cur1;
            }
        }
        return null;
    }

    public static void main(String[] args) {

    }

}
